import java.util.LinkedList;
import java.util.Queue;

public class Solution {
    int m = 0, n = 0;
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    Queue<int[]> q = new LinkedList<>();

    public int[][] updateMatrix(int[][] mat) {
        m = mat.length;
        n = mat[0].length;

        int[][] ret = new int[m][n];

        boolean[][] flag = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    q.offer(new int[]{i, j});
                }
            }
        }

        while (!q.isEmpty()) {
            int size = q.size();
            while (size > 0) {
                size--;
                int[] arr = q.poll();
                int x = arr[0];
                int y = arr[1];
                flag[x][y] = true;
                for (int i = 0; i < 4; i++) {
                    int xx = x + dx[i];
                    int yy = y + dy[i];
                    if (xx >= 0 && yy >= 0 && xx < m && yy < n && !flag[xx][yy] && mat[xx][yy] != 0) {
                        ret[xx][yy] = ret[x][y] + 1;
                        flag[xx][yy] = true;
                        q.offer(new int[]{xx, yy});
                    }
                }
            }
        }

        return ret;
    }

    public int[][] updateMatrix2(int[][] mat) {
        m = mat.length;
        n = mat[0].length;

        int[][] ret = new int[m][n];

        // boolean[][] flag = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                //初始化ret数组，就不需要使用flag标志数组
                ret[i][j] = -1;
                if (mat[i][j] == 0) {
                    q.offer(new int[]{i, j});
                }
            }
        }

        while (!q.isEmpty()) {
            int[] arr = q.poll();
            int x = arr[0];
            int y = arr[1];
            if (mat[x][y] == 0) {
                ret[x][y] = 0;
            }
            // flag[x][y] = true;
            for (int i = 0; i < 4; i++) {
                int xx = x + dx[i];
                int yy = y + dy[i];
                if (xx >= 0 && yy >= 0 && xx < m && yy < n && ret[xx][yy] == -1) {
                    if (mat[xx][yy] == 0) {
                        ret[xx][yy] = 0;
                    } else {
                        ret[xx][yy] = ret[x][y] + 1;
                        q.offer(new int[]{xx, yy});
                    }
                    // flag[xx][yy] = true;
                }
            }
        }


        return ret;
    }
}
